題目

2326. Spiral Matrix IV
難度: 中等偏易

題意

給定一鏈結串列head，及二整數m n。
回傳m * n大小的矩陣，從左上角開始，按照順時鐘螺旋(右下左上右)的順序填入head中的值，若填不完則剩於格子的都填入-1。

思路

如上述題意，可拆解為子問題:

1. 向右走到底
2. 向下走到底
3. 向左走到底
4. 向上走到底
5. 向右走一格
   每走完一圈，長寬各減二

每一圈如下圖

→→  ...  →⭣
↑→        ⭣
.         .
.         .
.         .
←←  ...  ←←

實作

簡單粗暴地刻出來~

class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> res(m, vector<int>(n, -1));
        
        // Current indexes
        int i = 0, j = 0;
        int round = 0;
        ListNode* curr = head;
        while(curr)
        {
            int rd = n - 1 - round * 2; // Right distance
            // Go right
            while(curr && rd > 0)
            {
                res[i][j] = curr->val;
                // Update indexes
                j++;
                rd--;
                curr = curr->next;
            }

            int dd = m - 1 - round * 2; // Down distance
            // Go down
            while(curr && dd)
            {
                res[i][j] = curr->val;
                // Update indexes
                i++;
                dd--;
                curr = curr->next;
            }

            int ld = n - 1 - round * 2; // Left distance
            // Go down
            while(curr && ld)
            {
                res[i][j] = curr->val;
                // Update indexes
                j--;
                ld--;
                curr = curr->next;
            }

            int ud = m - 1 - round * 2 - 1; // Up distance
            // Go down
            while(curr && ud)
            {
                res[i][j] = curr->val;
                // Update indexes
                i--;
                ud--;
                curr = curr->next;
            }

            // Go right and go next round
            if(curr)
            {
                res[i][j] = curr->val;
                j++;
                curr = curr->next;
            }

            round++;
        }

        return res;
    }
};

分析

若head長度為N，矩陣大小m * n
時間複雜度: O(mn + N)，初始化m * n矩陣，接著遍歷head
空間複雜度: O(1)，除了output無須額外空間

結果

Accepted
50/50 cases passed (159 ms)
Your runtime beats 73.51 % of cpp submissions
Your memory usage beats 17.37 % of cpp submissions (130.7 MB)